package algorithm.dp;

public class 最长回文子串 {
    /*
     * 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
     * 
     * 示例 1：
     * 
     * 输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。 示例 2：
     * 
     * 输入: "cbbd" 输出: "bb"
     */
    public String longestPalindrome(String s) {
        return dp(s);
    }

    /*
     * 执行用时 : 94 ms, 在Longest Palindromic Substring的Java提交中击败了43.82% 的用户 内存消耗 :
     * 49.1 MB, 在Longest Palindromic Substring的Java提交中击败了29.17% 的用户
     */
    public String dp(String s) {
        int len = s.length();
        if (len <= 1) {
            return s;
        }
        boolean[][] isPalindrome = new boolean[len][len];
        int mi = 0;
        int mj = 0;
        for (int j = 0; j < len; j++) {
            isPalindrome[j][j] = true;
            for (int i = j - 1; i >= 0; --i) {
                isPalindrome[i][j] = s.charAt(i) == s.charAt(j) && (i + 1 == j || isPalindrome[i + 1][j - 1]);
                if (isPalindrome[i][j] && (j - i > mj - mi)) {
                    mi = i;
                    mj = j;
                }
            }
        }
        return s.substring(mi, mj + 1);
    }

    String longest = "";

    /*
     * 中心法解决 执行用时 : 33 ms, 在Longest Palindromic Substring的Java提交中击败了61.66% 的用户
     * 内存消耗 : 45.1 MB, 在Longest Palindromic Substring的Java提交中击败了41.19% 的用户
     */
    public String longestPalindromeWithCenter(String s) {
        for (int i = 0; i < s.length(); i++) {
            center(s, i, i);
            center(s, i, i + 1);
        }
        return longest;
    }

    void center(String s, int i, int j) {
        // 中心法来找最长的
        boolean datasizeValid = i >= 0 && j < s.length();
        if (!datasizeValid || s.charAt(i) != s.charAt(j)) {
            if (j - i - 1 > longest.length() && i + 1 < j) {
                longest = s.substring(i + 1, j);
            }
        } else {
            center(s, i - 1, j + 1);
        }
    }

    public static void main(String[] args) {
        最长回文子串 run = new 最长回文子串();
        run.longestPalindrome("babad");
    }
}
